package com.leetcode.www;

import java.util.*;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集
 * User:yxd
 * Date:2022-04-23
 * Time:20:56
 */
public class DFS78 {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {//深度优先搜素
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }

    /*List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets2(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
*/
    public List<List<Integer>> subsets1(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] bool = new boolean[nums.length];//标记矩阵
        ret.add(new ArrayList<>(list));
        DFS(ret,list,nums,0,bool);
        return ret;
    }
    public void DFS(List<List<Integer>> ret,List<Integer> list,int[] nums,int index,boolean[] bool){
        if(!list.isEmpty()){
            ret.add(new ArrayList<>(list));
        }
        for(int i = index;i < nums.length;i ++){
            if(!bool[i]){
                bool[i] = true;
                list.add(nums[i]);
                DFS(ret,list,nums,i + 1,bool);
                bool[i] = false;
                list.remove(list.size() - 1);
            }

        }
    }
}
